package com.lyz.dataStructure.JianZhiOffer;/**
 * @Author:759057893@qq.com Lyz
 * @Date: ${Date} 16:00
 * @Description:
 **/

import java.util.HashSet;

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/6/23 16:00
 *@Description:
 **/

/*
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
 */
public class Test21 {
    public static ListNode EntryNodeOfLoop(ListNode head){
        if(head==null||head.next==null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                slow =head;
                while(slow!=fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                if(slow==fast) return slow;
            }
        }
        return null;
    }

    public static void main(String[] args) {
            ListNode root = new ListNode(1);
            ListNode node1 = new ListNode(2);
            ListNode node2 = new ListNode(3);
            ListNode node3 = new ListNode(4);
            ListNode node4 = new ListNode(5);

            root.next = node1;
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node2;
            System.out.println(EntryNodeOfLoop(root).val);
        }
    }

